package com.huawei.M01.iterator;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 表现良好时间段的最大长度
 *
 * @author 111
 */
public class LongestWPI2 {
    public int longestWPI(int[] hours) {
        int res = 0;
        // 构造一个前缀和数组
        int[] adds = new int[hours.length + 1];
        // 定义一个栈，用于存放前缀和大于栈顶元素的下标
        // 这是一个递减序列，可以存放
        Deque<Integer> stack = new ArrayDeque<>(hours.length + 1);
        stack.push(0);
        for (int i = 1; i <= hours.length; i++) {
            adds[i] = adds[i - 1] + (hours[i - 1] > 8 ? 1 : -1);
            if (adds[i] < adds[stack.peek()]) {
                stack.push(i);
            }
        }

        for (int r = hours.length; r >= 1; r--) {
            while (!stack.isEmpty() && adds[r] > adds[stack.peek()]) {
                res = Math.max(res, r - stack.pop());
            }
        }
        return res;
    }


    public static void main(String[] args) {
        LongestWPI2 longestWPI = new LongestWPI2();
        System.out.println(longestWPI.longestWPI(new int[]{6, 9, 9}));
    }
}
